1. Field of the Invention
The present invention relates, in general, to data processing systems and, more particularly, to the scheduling and dispatching of processes in parallel processing computer systems.
2. Description of the Related Technology
Parallel processing systems are able to execute two or more computer programs or processes simultaneously. In a parallel processing architecture, general-purpose multiprocessors are organized to cooperatively work together to execute multiple processes simultaneously. Although a variety of types of parallel processing architectures exist, it is traditional to classify parallel processing architectures into two broad categories: Single Instruction Multiple Data (SIMD) and Multiple Instruction Multiple Data (MIMD).
SIMD computers execute the same instruction on multiple data values simultaneously. It is well known in the art to implement SIMD computers using an array processor capable of operating on large two-dimensional matrices of data values in parallel by simultaneously applying the same operation to every element. SIMI) machines are well suited for performing matrix calculations necessary in finite-element analysis. SIMD machines have been used to perform seismic modeling, atmospheric modeling, and image processing calculations.
In contrast, MIMD computers use multiple processors executing different processes or sub-processes on different sets of data. For the following reasons, communication between multiple processors in a MIMD machine is crucial. First, if two or more processors execute sub-processes of the same process, facilities must be provided for coordinating the results obtained by the different processors. Second, the MIMD machine must be capable of assigning processes awaiting execution to available processors. Third, in systems using a process hierarchy, where some processes have higher processing priority than others, a facility must be provided to ensure that processors execute only the highest priority processes awaiting execution.
For example, some processes may require "real-time" processing, while others may not. In such a system, a process hierarchy may be established whereby real-time processes are assigned higher priority numbers than processes not requiring real-time execution. MIMD machines using a process hierarchy must have a facility for assigning the highest priority processes awaiting execution to either the next available processor, or, if there are no processors available, to a processor executing a lower priority process. Accordingly, MIMD machines using a process hierarchy must be capable of scheduling processes for execution, and interrupting processors executing lower priority processes than the processes scheduled for execution.
In parallel processing machines of the prior art, process scheduling is a complicated and processing intensive task. The more processors or processing systems used, the more complicated scheduling becomes. The goal of process scheduling, in general, is to ensure that the most important processes are always executed first. Accordingly, if a processor is executing a process of lower priority or significance than other processes awaiting execution, the process scheduler should interrupt that processor and cause it to execute the more important process.
It is well known in the art to implement schedulers in software. Software schedulers interrupt processors to determine whether those processors are performing the highest priority process possible. Software schedulers are used in systems having a central control unit; typically the software scheduler is stored in a central memory and executes on a central processing unit. Software implemented schedulers are exemplified by U.S. Pat. Nos. 3,496,551 and 3,348,210. Software schedulers of the prior art suffer from several disadvantages. First, software schedulers of the prior art perform poorly in multiprocessing systems that process a number of asynchronous events. A common example of an application requiring processing of many asynchronous events is a flight tester. Software schedulers are inadequate for scheduling processes in this environment because too many asynchronous events cause continuous processor interruption, which in turn causes the processors to spend more time scheduling and less time executing useful programs.
A second disadvantage of software schedulers of the prior art occurs when the schedulers enter a "thrash mode". "Thrashing" occurs when the software scheduler fails to take into account higher priority processes needing to be scheduled during the course of scheduling a previous process awaiting execution. In these thrashing situations, the scheduling time can exceed 50% of the process execution time (the time a processor is actually executing a process). A third disadvantage of software schedulers of the prior art is system processing speed. Because software schedulers of the prior art are programs having instructions which must be executed sequentially, the prior art schedulers execute slowly. Slow scheduler execution time adversely affects systems which must process instructions in real-time. Another disadvantage of software schedulers of the prior art is development cost. Software schedulers suffer from the high costs of control programming necessary to support scheduler operation. Complicated process scheduling programs are necessary to perform complex multiprocessing operations. Therefore, the development costs associated with software process schedulers of the prior art are significant. Furthermore, as the software process scheduler becomes more complex, the more difficult it is to maintain, and the more unreliable the multiprocessing system becomes. Finally, software schedulers do not take advantage of the improvements made in very large-scale integrated (VLSI) circuit technology.
It is also well known in the prior art to implement process schedulers in firmware. Firmware process schedulers use special-purpose micro-programmed controllers to perform scheduling and dispatching operations. Firmware process schedulers are exemplified by U.S. Pat. Nos. 4,011,545, 3,959,775, and 3,896,418. The disadvantage of the firmware implemented process schedulers of the prior art is a lack of flexibility. Firmware process schedulers also lack general purpose application because they are typically designed to execute special-purpose tasks. Another disadvantage of firmware schedulers is that they do not allow for execution of "multi-threaded" processes; i.e. processes which run on several processors simultaneously.
Process schedulers have also been implemented in hardware. Hardware process schedulers are exemplified by U.S. Pat. No. 4,387,427. Hardware schedulers suffer from various disadvantages. First, as with firmware solutions, hardware schedulers also lack flexibility. For example, in the referenced patent, processes must first be assigned complex access descriptors in order to gain access to available processors. Second, hardware schedulers are typically only able to schedule synchronous events because they lack the necessary mechanisms for effectively communicating between asynchronous operations. Another disadvantage of hardware schedulers is that they do not allow for flexible process hierarchies.
Therefore, the need has arisen for a hardware process scheduler that eliminates the use of scheduling software, provides for flexible process scheduling, ensures that all processors always execute the most important processes first, dispatches processes to processors quickly and efficiently, accommodates multiprocessing systems using process hierarchies, accommodates asynchronous processing, operates on real-time processes, takes advantage of advances in VLSI technology, permits multi-threaded process execution, and is easily and inexpensively implemented.